22.3-2

22.3-3

$(u$ $(v$ $(y$ $(x$ $x)$ $y)$ $v)$ $u)$ $(w$ $(z$ $z)$ $w)$

22.4-3

Design:

Algorithm($G$):
  for each vertex $u \in G$.$V$:
    $u.$color $:=$ WHITE
    $u$.$\pi := $ NIL

  time $:= 0$
  for each $u \in G$.$V$:
    if $u.$color == WHITE
      if MODIFIED-DFS-VISIT($u$) == True:
        return True
  return False

MODIFIED-DFS-VISIT($u$):
  time $:=$ time $+ 1$
  $u$.d $:=$ time
  $u$.color $:=$ GRAY
  for each $v \in G$.$Adj[u]$:
    if $v$.color == WHITE
      $v$.$\pi := u$
      if MODIFIED-DFS-VISIT($v$) == True:
        return True
    else
      return True

  $u$.color $:=$ BLACK
  $u$.$f := $ time $:=$ time $+1$
  return False

Analysis:

1. Our algorithm visits each node in $V$ at most twice when it returns answer.
2. The depth-first tree contains $|V_{\text{DFS}}| - 1$ edges. When our algorithm terminates, it has gone through at most $|V|$ edges.
   Hence, the time complexity is $O(|V|)$.

22.5-3

If so, the second DFS might cross different SCCs.

For example, let $C_1$, $C_2$ be two different SCCs with circular shape, we may assume $C_1$.$V = \{u_1, ... , u_n\}$ and there exists an edge $(u_k, v)$ satisfying $u_k \in C_1$, $v \in C_2$. Assuming that we start the first DFS from $u_{k+2}$ but enter $C_2$ after it visits all nodes in $C_1$.

Thus, we have two chain-like depth-first trees $T_1$ and $T_2$ which contain all nodes of $C_1$ and $C_2$, respectively. And it does not pass through $(u_k,v)$. Note that the node with smallest finishing time must be $u_{k+1}$, then the second DFS will start from $u_{k+1}$ and turn in $(u_k,v)$ then get exceed $C_1$ after it goes through $u_k$.

22-2

c.

Design:

Algorithm($G$, $G_\pi$):
  let $E_r := G$.$E - G_\pi$.$E_\pi$
  let $G_r := (V, E_r)$
  let root $:= G_\pi$.$V$
  root.low $:=$ Visit($G_\pi$, $E_r$, root)
  if root has at least $2$ children:
    output root

Visit($G_\pi$, $G_r$, $v$):
  min $:= \infty$
  for each $u \in G_\pi$.$Adj[v]$ but $u \neq v$.$\pi$:
    temp $:=$ Visit($u$)
    if temp $<$ min:
      min $:=$ temp
  for each $w \in G_r$.$Adj[v]$:
    if $w$.$d < $ min:
      min $:= w$.$d$
  $v$.low $:= \min${min, $v$.$d$}
  if $v$.$d \leq v$.low:
    output $v$
  return min

Analysis:

1. $G$ is connected. $\implies |V|=O(|E|)$
   
2. Our algorithm goes through each node & edge at most twice. $\implies O(|E|)$

Hence, the time complexity is $O(|E|)$.

d.

As above. Output all nodes $v$ satisfying $v$.$d$ == $v$.low.
Since $G$ is connected. $\implies$ The complexity is $|V|=O(|E|)$

h.

If node $u$ is contained in a BCC, then $u$.low $\leq u$.$d$ and all other nodes which have the same low value are also contained in this BCC.

Design:

Algorithm($G$, $G_\pi$):
  use c. to evaluate all nodes' low value
  for each $v \in V$:
    $v$.bcc := $v$.low

Analysis:

1. The algorithm of c. takes $O(|E|)$ time.
   
2. The for-loop takes $O(|V|)$ time.
   Hence, the time complexity is $O(|E|)$.